Network traffic engineering (TE) is a method for controlling network traffic, so as to achieve some specific holistic objectives in a network, for example, optimizing network utilization, balancing network utilization, reducing network congestion, and reducing network load.
To achieve the holistic objectives in the network, a most common TE implementation method is to estimate (or collect statistics about) all source and destination connection requirements in the entire network, and then use various routing mechanisms (or network protocols) to perform optimization according to a TE objective. As a network scale is increasing, an original TE method has huge computational complexity, and feasibility of performing all TE steps is extremely low. For example, most typical routing protocols used in the Internet are all generated based on the following two mechanisms:
a distance vector routing protocol, such as the Routing Information Protocol (RIP) or the Border Gateway Protocol; and a link state (Link State) routing protocol, such as the Open Shortest Path First protocol.
However, an existing routing protocol may have excessively high computational complexity (especially for a large-scale network). For example, the distance vector routing protocol uses the Bellman-Ford (Bellman-Ford) algorithm and features complexity of O(|V|*|E|), where |V| is a quantity of nodes (number of nodes), and |E| is a quantity of edges (number of edges); the link state routing protocol usually uses some variants of the Dijkstra algorithm and features complexity of O(|E|+|V|log|V|). In these routing protocols, a method for calculating a best path is setting a short-term link cost to a cost related to a distance from a destination. However, in TE, these algorithms further need to run repeatedly to update the short-term link cost, so as to implement the specific objectives for entire-network control. This manifests excessively high complexity. In actual application, a network traffic engineer usually uses a manual trial-out method to update the short-term link cost. The procedure is extremely complicated and cannot be implemented in the large-scale network. Some existing types of TE are implemented by using a Multiprotocol Label Switching (MPLS) method, but require a cost for establishing a link label. Although the existing routing protocol does not repeatedly run in MPLS, the label needs to be repeatedly updated to implement a TE optimization objective. These are only some examples, and actual TE implementation depends on the network traffic engineer. For example, during selection, the network traffic engineer may use some variants of the foregoing protocols, for example, change the link cost or an objective, or allow for multiple paths, so as to implement a TE objective. However, repeated running of these algorithms cannot be avoided. As the network scale increases, if all TE steps, that is, from estimating an entire-network link traffic requirement to optimizing entire-network routing according to the TE objective, need to be completed, original TE is no longer applicable because of its huge complexity.
In addition, the entire-network link traffic requirement required in network traffic engineering is estimated based on network status data. If a TE algorithm runs slowly, effective network status information used in TE is actually limited (sparse) as a network status changes, even when the network status data is sampled at a high frequency. However, all existing TE technologies are based on an assumption that the network status data is sufficient and unchanged. When there is only sparse network status data, it is difficult to implement TE control according to an original entire-network-based algorithm.
Basically, all networks have TE problems. Because a software defined network (SDN) is an important constructable structure for a future network, the following uses the SDN network as an example to describe an existing TE problem. The SDN separates a control plane from a data plane. Because an SDN controller provides relatively strong network controllability (unlike a previous distributed network, the SDN uses a centralized controller architecture), TE efficiency in the SDN is higher than that in an existing network. However, to achieve (potentially) best TE efficiency in the SDN (at least higher than TE efficiency in the existing network), the prior art also needs to be based on the entire network's status.
For the SDN network, the SDN has a centralized architecture (so that TE efficiency in the SDN is higher than that in the existing network). Before TE control is performed, an entire-network traffic requirement needs to be estimated. If all related information required in TE in the entire network is sampled and fed back to the SDN controller, extremely high overheads may be required for measurement data feedback. In addition, a validity period of the information is usually shorter than a TE operation time (because as described above, the SDN controller requires a large quantity of operations because of high computational complexity, a network scenario change is normal before an operation result is obtained). In addition, an existing SDN technology requires complete network information (which usually requires intensive sampling), and further it is required to assume that the network information is an invariant (that is, a constant) during a TE control operation. It is difficult to implement TE control according to the original entire-network-based algorithm.
To reduce a large amount of unnecessary measurement and feedback and achieve the TE objective in real time, a most important problem is how to set some general TE optimization objectives that can use downsampled data having low feedback overheads and that can be achieved by using an algorithm having low complexity in an environment of low sampling and low feedback overheads, and to achieve an effect equivalent to an expected TE effect in the entire SDN in an entire observable environment.
Therefore, in the existing network, how to implement TE based on partial measurement becomes a problem that needs to be urgently resolved.